package algorithm.leetcode.medium;

/*
 给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），
 并返回该子数组所对应的乘积。
 */

/**
 * @author jack.wu
 * @version 1.0
 * @date 2020/12/28
 */
public class Question152 {

    public static void main(String[] args) {
        int[] nums = {2,3,-2,4};
        Question152 question = new Question152();
        int product = question.maxProduct(nums);
        System.out.println(product);
    }

    public int maxProduct(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int max = Integer.MIN_VALUE;
        int curMax = 1;
        int curMin = 1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] < 0) {
                // 如果当前项是负数 最大乘积 = 之前最小的乘积 * 当前负数
                int temp = curMax;
                curMax = curMin;
                curMin = temp;
            }
            // 子数组最大乘积 = curMax * nums[i]， 有可能重新开始nums[i]
            curMax = Math.max(curMax * nums[i], nums[i]);
            // 考虑负数 所以这里记录最小乘积
            curMin = Math.min(curMin * nums[i], nums[i]);
            // 更新最大值
            max = Math.max(max, curMax);
        }
        return max;
    }

}
